package 左哥算法.ch10暴力递归;

import org.junit.Test;

import java.util.Stack;

public class Ch01一些递归题 {

    /**
     * ch02：给你一个栈，请你逆序这个栈，不能申请额外的数据结构
     * 思路：
     * 定义一个方法，方法可以将栈底元素抽出来，将其他元素压下去。
     * 1.调用这个方法抽出底部元素，
     * 2.递归调用自己让栈中其他元素逆序
     * 3.压入底部元素
     */
    @Test
    public void test02() {
        Stack<String> stack = new Stack<>();
        stack.push("a");
        stack.push("b");
        stack.push("c");
        stack.push("d");
        reversal(stack);
        System.out.println(stack);
    }

    public void reversal(Stack<String> stack) {
        if (stack.isEmpty()) {
            return;
        }
        String bottom = drawOut(stack);
        reversal(stack);
        stack.push(bottom);
    }

    /**
     * 抽取底部元素，将其他元素下压(过程有点难理解)
     * 他的实现步骤：
     * 1.先将栈顶元素取出
     * 2.调用自身将栈底元素抽出
     * 3.将栈顶元素押回
     * 4.返回抽出的元素
     * 直到仅剩一个元素
     * （我不理解1和3对母问题的影响）
     */
    public String drawOut(Stack<String> stack) {
        String result = stack.pop();
        if (stack.isEmpty()) {
            return result;
        }
        String last = drawOut(stack);
        stack.push(result);
        return last;
    }
}
